package codeRandomThoughts.Test450删除二叉搜索树中的节点;

import codeRandomThoughts.utils.TreeNode;

public class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if (root == null) return null;
        if (root.val == key) {//遍历到了要删除的结点
            //1.叶子结点
            if (root.left == null && root.right == null) {
                return null;
            }

            //2.结点只有左子树
            else if (root.left != null && root.right == null) {
                return root.left;
            }

            //3.结点只有右子树
            else if (root.left == null) {
                return root.right;
            }

            //4.结点左右子树都有,这边选择把左子树接到右子树最靠左的结点上
            else {
                TreeNode left = root.left;
                TreeNode right = root.right;
                while (right.left != null) {
                    right = right.left;
                }
                right.left = left;
                return root.right;
            }
        }

        //拼接新生成的二叉树
        else if (key < root.val) {
            root.left = deleteNode(root.left, key);
        } else {//key肯定大于root.val
            root.right = deleteNode(root.right, key);
        }
        return root;
    }
}
